﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MatrixGraph
{
	public class Program
	{
		static void Main(string[] args)
		{
			MatrixGraphManager manager = new MatrixGraphManager();
			//创建图
			MatrixGraph graph = manager.CreateMatrixGraph();
			manager.OutMatrix(graph);
			Console.Write("广度递归:\t");
			manager.BFSTraverse(graph); 
			Console.Write("\n深度递归:\t");
			manager.DFSTraverse(graph);
			Console.ReadLine();
		}
	}

	#region 邻接矩阵的结构图

	public class MatrixGraph
	{
		//保存定点的信息
		public string[] vertex;
		//保存边信息
		public int[,] edges;
		//深搜和广搜的遍历标志
		public bool[] isTrav;
		//顶点数量
		public int vertexNum;
		//边数量
		public int edgeNum;
		//图类型
		public int graphType;

		/// <summary>
		/// 存储容量的初始化
		/// </summary>
		/// <param name="vertexNum"></param>
		/// <param name="edgeNum"></param>
		/// <param name="graphType"></param>
		public MatrixGraph(int vertexNum,int edgeNum,int graphType)
		{
			this.vertexNum = vertexNum;
			this.edgeNum = edgeNum;
			this.graphType = graphType;

			vertex=new string[vertexNum];
			edges=new int[vertexNum,edgeNum];
			isTrav=new bool[vertexNum];
		}
	}

	#endregion

	#region 图的操作类

	public class MatrixGraphManager
	{
		#region 图的创建
		
		public MatrixGraph CreateMatrixGraph()
		{
			Console.WriteLine("请输入创建图的顶点个数，边个数，是否为无向图(0,1来表示)，已逗号隔开。");
			var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
			MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);
			Console.WriteLine("请输入各顶点信息：");
			for (int i = 0; i < graph.vertexNum; i++)
			{
				Console.Write("\n第" + (i + 1) + "个顶点为:");
				var single = Console.ReadLine();
				//顶点信息加入集合中
				graph.vertex[i] = single;
			}
			Console.WriteLine("\n请输入构成两个顶点的边和权值，以逗号隔开。\n");
			for (int i = 0; i < graph.edgeNum; i++)
			 {
				Console.Write("第" + (i + 1) + "条边:\t");
				initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();
				int start = initData[0];
				int end = initData[1];
				int weight = initData[2];
				//给矩阵指定坐标位置赋值
				graph.edges[start - 1, end - 1] = weight;
				//如果是无向图，则数据呈“二，四”象限对称
				if (graph.graphType == 1)
				{
					graph.edges[end - 1, start - 1] = weight;
				}
			 }
			return graph;
		}

		#endregion

		#region 输出矩阵数据
		/// <summary>
		/// 输出矩阵数据
		/// </summary>
		/// <param name="graph"></param>
        public void OutMatrix(MatrixGraph graph)
        {
            for (int i = 0; i < graph.vertexNum; i++)
            {
                for (int j = 0; j < graph.vertexNum; j++)
                {
                    Console.Write(graph.edges[i, j] + "\t");
                }
                //换行
                Console.WriteLine();
            }
        }

        #endregion

		#region 广度优先

		/// <summary>
		/// 广度优先
		/// </summary>
		/// <param name="graph"></param>
        public void BFSTraverse(MatrixGraph graph)
        {
            //访问标记默认初始化
            for (int i = 0; i < graph.vertexNum; i++)
            {
                graph.isTrav[i] = false;
            }
            //遍历每个顶点
            for (int i = 0; i < graph.vertexNum; i++)
            {
                //广度遍历未访问过的顶点
                if (!graph.isTrav[i])
                {
                    BFSM(ref graph, i);
                }
            }
        }
 
		/// <summary>
		/// 广度遍历具体算法
		/// </summary>
		/// <param name="graph"></param>
         public void BFSM(ref MatrixGraph graph, int vertex)
         {
             //这里就用系统的队列
             Queue<int> queue = new Queue<int>();
             //先把顶点入队
             queue.Enqueue(vertex);
             //标记此顶点已经被访问
             graph.isTrav[vertex] = true;
             //输出顶点
             Console.Write(" ->" + graph.vertex[vertex]);
             //广度遍历顶点的邻接点
             while (queue.Count != 0)
             {
                 var temp = queue.Dequeue();
                 //遍历矩阵的横坐标
                 for (int i = 0; i < graph.vertexNum; i++)
                 {
                     if (!graph.isTrav[i] && graph.edges[temp, i] != 0)
                     {
                         graph.isTrav[i] = true;
                         queue.Enqueue(i);
                         //输出未被访问的顶点
                         Console.Write(" ->" + graph.vertex[i]);
                     }
                 }
             }
         }

         #endregion

		#region 深度优先

		/// <summary>
		/// 深度优先遍历
		/// </summary>
		/// <param name="graph"></param>
		public void DFSTraverse(MatrixGraph graph)
        {
			//访问标记默认初始化
			for (int i = 0; i < graph.vertexNum; i++)
			{
				graph.isTrav[i] = false;
			} 
			//遍历每个顶点
			for (int i = 0; i < graph.vertexNum; i++)
			{
				//广度遍历未访问过的顶点
				if (!graph.isTrav[i])
				{
					DFSM(ref graph, i);
				}
			}
        }

		/// <summary>
		/// 深度递归的具体算法
		/// </summary>
		/// <param name="graph"></param>
		/// <param name="vertex"></param>
		public void DFSM(ref MatrixGraph graph, int vertex)
        {
			Console.Write("->" + graph.vertex[vertex]);
			//标记为已访问
			graph.isTrav[vertex] = true;
			//要遍历的六个点
			for (int i = 0; i < graph.vertexNum; i++)
			{
				if (graph.isTrav[i] == false && graph.edges[vertex, i] != 0)
				{
					//深度递归
					DFSM(ref graph, i);
				}
			}
        }
		#endregion
	}

	#endregion
}
